package cn.bellychang.leetcode.question1011;

import java.util.Arrays;

/**
 *
 * A conveyor belt has packages that must be shipped from one port to another within D days.
 *
 * The ith package on the conveyor belt has a weight of weights[i].
 * Each day, we load the ship with packages on the conveyor belt (in the order given by weights).
 * We may not load more weight than the maximum weight capacity of the ship.
 *
 * Return the least weight capacity of the ship that will result in all the packages on the conveyor belt being shipped within D days.
 *
 * @author ChangLiang
 * @date 2021/2/3
 */
public class Solution {

    public int shipWithinDays(int[] weights, int D) {

        int max = Arrays.stream(weights).max().getAsInt();
        int sum = Arrays.stream(weights).sum();

        int capacityL = max;
        int capacityR = sum;

        while (capacityL < capacityR) {
            int middle = (capacityR - capacityL) / 2 + capacityL;
            if (getDays(weights, middle) > D) {
                // capacity small
                capacityL = middle + 1;
            } else {
                // <=D  the least capacity
                capacityR = middle;
            }
        }
        return capacityL;
    }

    public int getDays(int[] weights, int capacity) {
        int days = 0;
        int daySum = 0;
        for (int i = 0; i < weights.length; i++) {
            int res = capacity - daySum;
            // 说明还可以放进来
            if (weights[i] <= res) {
                daySum += weights[i];
            }else{
                days++;
                daySum = 0;
                i--;
            }
        }
        if (daySum != 0) {
            days++;
        }
        return days;
    }
}
